/*
Abstract:
  DizPack implementation

Last changed:
  $Id: dizpack.cpp 82 2009-12-08 20:53:44Z vitamin.caig $

Author:
  (C) Vitamin/CAIG/2001
  (C) Original idea from Dizzy gameset

  This file is the part of Textator project
*/
#include "packer.h"

#include <tools.h>

#include <cassert>
#include <numeric>
#include <algorithm>

namespace
{
  typedef std::vector<unsigned char> Dump;

  const String::value_type DIZPACK_TABLENAME[] = {'_', 'D', 'I', 'Z', 'P', 'A', 'C', 'K', '_', 0};
  const unsigned DumpSymbols(1 << 8 * sizeof(Dump::value_type));

  struct SymbolStat
  {
    SymbolStat(unsigned sym, unsigned frq) : Symbol(sym), Freq(frq)
    {
    }
    unsigned Symbol;
    unsigned Freq;
    
    unsigned GetSymbol() const
    {
      return Symbol;
    }
  };

  inline bool ReverseSortByFreq(const SymbolStat& lh, const SymbolStat& rh)
  {
    return lh.Freq > rh.Freq;
  }

  typedef std::vector<SymbolStat> StatArray;

  class CalcStat : public std::unary_function<StringMap::value_type, void>
  {
  public:
    explicit CalcStat(StatArray& data) : Stat(data)
    {
    }

    result_type operator ()(const argument_type& arg) const
    {
      for (StrIterator<String> it(arg.second); it; ++it)
      {
        String::value_type sym(*it);
        for (unsigned bt = 0; bt != sizeof(String::value_type) / sizeof(Dump::value_type); ++bt, sym >>= 8)
        {
          ++Stat[sym & 0xff].Freq;
        }
      }
    }
  private:
    StatArray& Stat;
  };

  void BuildModel(const StringMap& input, StatArray& model)
  {
    assert(model.empty());
    StatArray statistic;
    statistic.reserve(DumpSymbols);
    model.reserve(DumpSymbols);
    for (unsigned byt = 0; byt < DumpSymbols; ++byt)
    {
      statistic.push_back(SymbolStat(byt, 0));
    }
    std::for_each(input.begin(), input.end(), CalcStat(statistic));
    std::sort(statistic.begin(), statistic.end(), ReverseSortByFreq);
    StatArray::iterator lastOne(std::upper_bound(statistic.begin(), statistic.end(), SymbolStat(0, 1), ReverseSortByFreq));
    model.assign(statistic.begin(), lastOne);
  }

  class Encoder : public std::unary_function<String::value_type, unsigned>
  {
  public:
    explicit Encoder(const StatArray& model) : Model(model), Lookup(DumpSymbols)
    {
      for (result_type idx = 0; idx != Model.size(); ++idx)
      {
        Lookup[Model[idx].Symbol] = idx;
      }
    }

    result_type operator()(const argument_type val) const
    {
      return Lookup[val];
    }
  private:
    const StatArray& Model;
    std::vector<result_type> Lookup;
  };

  class NibblePacker : public std::unary_function<unsigned, void>
  {
  public:
    explicit NibblePacker(const StatArray& model) : Coder(model), Target(), Buf(), Filled()
    {
    }
    
    void Start()
    {
      Target.clear();
      Buf = 0;
      Filled = false;
    }

    const Dump& Finish()
    {
      if (Filled)
      {
        PutNibble(15);
      }
      return Target;
    }

    result_type operator()(argument_type arg)
    {
      for (unsigned bt = 0; bt != sizeof(String::value_type) / sizeof(Dump::value_type); ++bt, arg >>= 8)
      {
        PutSymbol(Coder(arg & 0xff));
      }
    }
  private:
    void PutSymbol(unsigned arg)
    {
      while (arg > 14)
      {
        PutNibble(15);
        arg -= 15;
      }
      PutNibble(arg);
    }

    void PutNibble(unsigned arg)
    {
      assert(arg < 16);
      Buf = (Buf << 4) | arg;
      Filled = !Filled;
      if (!Filled)
      {
        Target.push_back(Buf);
        Buf = 0;
      }
    }
  private:
    const Encoder Coder;
    Dump Target;
    unsigned Buf;
    bool Filled;
  };

  inline EntriesMap::value_type Dump2Entry(const String& name, const Dump& data)
  {
    return EntriesMap::value_type(name, Entry(Entry::GLOBAL, Token::BINARY, String(data.begin(), data.end())));
  }

  template<class StreamPacker>
  class PairPacker : public std::unary_function<StringMap::value_type, EntriesMap::value_type>
  {
  public:
    explicit PairPacker(StreamPacker& packer) : Packer(packer)
    {
    }

    result_type operator ()(const argument_type& arg) const
    {
      Packer.Start();
      std::for_each(arg.second.begin(), arg.second.end(), RefWrap(Packer));
      return Dump2Entry(arg.first, Packer.Finish());
    }
  private:
    StreamPacker& Packer;
  };

  inline StringMap::value_type AddZero(const StringMap::value_type& val)
  {
    return IsSpecialToken(val.first) ? val : StringMap::value_type(val.first, val.second + '\0');
  }

  inline std::size_t SumBinsize(std::size_t val, const EntriesMap::value_type& item)
  {
    return IsSpecialToken(item.first) ? val : val + item.second.Value.front().Value.size();
  }
}

namespace Packer
{
  void DizPack(const StringMap& input, EntriesMap& result, Statistic::Packing& statistic)
  {
    StringMap zeroed;
    std::transform(input.begin(), input.end(), std::inserter(zeroed, zeroed.end()), AddZero);
    StatArray model;
    BuildModel(zeroed, model);
    NibblePacker packer(model);
    std::transform(zeroed.begin(), zeroed.end(), std::inserter(result, result.end()), PairPacker<NibblePacker>(packer));
    statistic.ResultSize = std::accumulate(result.begin(), result.end(), 0, SumBinsize);
    Dump modelDump(model.size());
    std::transform(model.begin(), model.end(), modelDump.begin(), std::mem_fun_ref(&SymbolStat::GetSymbol));
    result.insert(Dump2Entry(DIZPACK_TABLENAME, modelDump));
    statistic.SupplementSize = modelDump.size();
  }
  //TODO: try to use another packing models
}
